\chapter{Network Analysis}

\section{Introduction}
Trees and network analysis here.


\section{Graph Analysis}
One of the basic rules of a successful representation is to separate
the nodes and the edges, to avoid DKNF problems. Thus, we create two
tables: 

\section{Graph Analysis in SQL}

\begin{verbatim}
CREATE TABLE nodes (
 id INTEGER PRIMARY KEY,
 name VARCHAR(10) NOT NULL,
 feat1 CHAR(1), -- e.g., age
 feat2 CHAR(1)  -- e.g., school attended or company
);
 
CREATE TABLE edges (
 a INTEGER NOT NULL REFERENCES nodes(id) ON UPDATE CASCADE ON DELETE CASCADE,
 b INTEGER NOT NULL REFERENCES nodes(id) ON UPDATE CASCADE ON DELETE CASCADE,
 PRIMARY KEY (a, b)
);
 
CREATE INDEX a_idx ON edges (a);
CREATE INDEX b_idx ON edges (b);
\end{verbatim}

The first table (nodes) contains the actual node payload, with all the
interesting information we need to store about a node (in the example,
feat1 and feat2 represent two node features, like the age of the
person, or the location, etc.). 

If we want to represent an undirected graph, we need to add a CHECK
constraint on the uniqueness of the pair. 

Since the SQL standard does not allow a subquery in the CHECK
constraint, we first create a function and then we use it in the CHECK
constraint (this example is for PostgreSQL, but can be easily ported
to other DBMS): 

\begin{verbatim}
CREATE FUNCTION check_unique_pair(IN id1 INTEGER, IN id2 INTEGER)
RETURNS INTEGER AS $body$ 
DECLARE retval INTEGER DEFAULT 0;
BEGIN
SELECT COUNT(*) INTO retval FROM (
  SELECT * FROM edges WHERE a = id1 AND b = id2
  UNION ALL
  SELECT * FROM edges WHERE a = id2 AND b = id1
) AS pairs;
RETURN retval;
END
$body$
LANGUAGE 'plpgsql';
 
ALTER TABLE edges ADD CONSTRAINT unique_pair CHECK
(check_unique_pair(a, b) < 1); 
\end{verbatim}

NB: a UDF in a CHECK constraint might be a bit slow [4]. An
alternative is to have a materialized view [5] or force an order in
the node pair (i.e. “CHECK (a < b)”, and then using a stored procedure
to insert the nodes in the correct order). 

If we also want to prevent self-loops (i.e. a node linking to itself),
we can add another CHECK constraint: 

ALTER TABLE edges ADD CONSTRAINT CHECK (a <> b)

\subsection{Traversing the Graph}

Now that we know how to store the graph, we might want to know which
nodes are connected. 

Listing the directly connected nodes is very simple:

\begin{verbatim}
SELECT *
  FROM nodes n
  LEFT JOIN edges e ON n.id = e.b
 WHERE e.a = 1;  -- retrieve nodes connected to node 1
\end{verbatim}

or, in the case of undirected edges:

\begin{verbatim}
SELECT * FROM nodes WHERE id IN (
  SELECT a FROM edges WHERE b = 1
  UNION
  SELECT b FROM edges WHERE a = 1
);
\end{verbatim}

-- or alternatively:
\begin{verbatim} 
SELECT * FROM nodes WHERE id IN (
    SELECT CASE WHEN a = 1 THEN b ELSE a END
      FROM edges
     WHERE 1 IN (a, b)
);
\end{verbatim}

Traversing the full graph usually requires more than a query: we can
either loop through the connected nodes, one level a time, or we can
create a temporary table holding all the possible paths between two
nodes. 

We could use Oracle’s CONNECT BY syntax or SQL standard’s Common Table
Expressions (CTEs) to recurse through the nodes, but since the graph
can contain loops, we’d get errors (unless we’re very careful, as
we’ll see in a moment). 

Kendall Willets [2] proposes a way of traversing (BFS) the graph using
a temporary table. It is quite robust, since it doesn’t fail on graphs
with cycles (and when dealing with trees, he shows there are better
algorithms available). His solution is just one of the many available,
but quite good. 

The problem with temporary tables holding all the possible paths is it
has to be maintained. Depending on how frequently the data is accessed
and updated it might still be worth it, but it’s quite expensive. If
you do resort to such a solution, these references may be of use [13]
[14]. 
As already mentioned, SQL has historically been unable [3] to express
recursive functions needed to maintain the transitive closure of a
graph without an auxiliary table. There are many solutions to solve
this problem with a temporary table (some even elegant [2]), but I
still haven’t found one to do it dynamically. 

Here’s my clumsy attempt at a possible solution using CTEs

First, this is how we can write the WITH RECURSIVE statement for a
Directed (Cyclic) Graph: 

\begin{verbatim}
WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
( SELECT a, b, 1 AS distance,
    a || '.' || b || '.' AS path_string
  FROM edges
 
  UNION ALL
 
  SELECT tc.a, e.b, tc.distance + 1,
  tc.path_string || e.b || '.' AS path_string
  FROM edges AS e
    JOIN transitive_closure AS tc
      ON e.a = tc.b
  WHERE tc.path_string NOT LIKE '%' || e.b || '.%'
)
SELECT * FROM transitive_closure
ORDER BY a, b, distance;
\end{verbatim}

Notice the WHERE condition, which stops the recursion in the presence
of loops. This is very important to avoid errors. 

One of the fundamental characteristics of networks (or graphs in
general) is connectivity. We might want to know how to go from A to B,
or how two people are connected, and we also want to know how many
“hops” separate two nodes, to have an idea about the distance.

For instance, social networks like LinkedIN show our connections or
search results sorted by degree of separation, and trip planning sites
show how many flights you have to take to reach your destination,
usually listing direct connections first. 

There are some database extensions or hybrid solutions like SPARQL on
Virtuoso [11] that add a TRANSITIVE clause [12] to make this kind of
queries both easy and efficient, but we want to see how to reach the
same goal with standard SQL. 

As you might guess, this becomes really easy once you have the
transitive closure of the graph, we only have to add a WHERE clause
specifying what our source and destination nodes are: 

\begin{verbatim}
WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
( SELECT a, b, 1 AS distance,
         a || '.' || b || '.' AS path_string
  FROM edges
 WHERE a = 1 -- source
 
  UNION ALL
 
  SELECT tc.a, e.b, tc.distance + 1,
         tc.path_string || e.b || '.' AS path_string
  FROM edges AS e
  JOIN transitive_closure AS tc ON e.a = tc.b
 WHERE tc.path_string NOT LIKE '%' || e.b || '.%'
)
  SELECT * FROM transitive_closure
   WHERE b=6 -- destination
ORDER BY a, b, distance;
\end{verbatim}

NB: setting the WHERE condition for the source node in the first part
of the CTE is way more efficient than moving it out of the VIEW, since
the selectivity is much higher and you avoid retrieving nodes you
don’t need. 
This query will return all paths from A to B, sorted by distance. 

Facebook: you might also know

A similar but slightly different requirement is to find those nodes
that are most strongly related, but not directly connected yet. 
In other words, it’s interesting to find out which and how many
connected nodes are shared between any two nodes, i.e. how many
“friends” are shared between two individuals. 
Or better yet, to find those nodes sharing a certain (minimum) number
of nodes with the current one. This could be useful to suggest a new
possible friend, or in the case of recommendation systems, to suggest
a new item/genre that matches the user’s interests. There are many
ways of doing this. In theory, this is bordering on the domain of
collaborative filtering [6][7][8], so using Pearson’s correlation [9]
or a similar distance measure with an appropriate algorithm [10] is
going to generate the best results. Collaborative filtering is an
incredibly interesting topic on its own, but outside the scope of this
article. A rough and inexpensive alternative is to find the nodes
having distance equals to 2, and filter those that either have a
common charateristic with the source node (went to the same school /
worked at the same company, belong to the same interest group / are
items of the same genre) or have several mutual “friends”. 

\begin{verbatim}
SELECT a AS you, b AS mightknow,  shared_connection,
       CASE
         WHEN (n1.feat1 = n2.feat1 AND n1.feat1 = n3.feat1) THEN
'feat1 in common' 
         WHEN (n1.feat2 = n2.feat2 AND n1.feat2 = n3.feat2) THEN
'feat2 in common' 
         ELSE 'nothing in common'
       END AS reason
  FROM (
WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
( SELECT a, b, 1 AS distance,
         a || '.' || b || '.' AS path_string,
         b AS direct_connection
    FROM edges2
   WHERE a = 1 -- set the starting node
 
   UNION ALL
 
  SELECT tc.a, e.b, tc.distance + 1,
         tc.path_string || e.b || '.' AS path_string,
         tc.direct_connection
    FROM edges2 AS e
    JOIN transitive_closure AS tc ON e.a = tc.b
   WHERE tc.path_string NOT LIKE '%' || e.b || '.%'
     AND tc.distance < 2
)
SELECT a,
       b,
       direct_connection AS shared_connection
  FROM transitive_closure
 WHERE distance = 2
) AS youmightknow
LEFT JOIN nodes AS n1 ON youmightknow.a = n1.id
LEFT JOIN nodes AS n2 ON youmightknow.b = n2.id
LEFT JOIN nodes AS n3 ON youmightknow.shared_connection = n3.id
WHERE (n1.feat1 = n2.feat1 AND n1.feat1 = n3.feat1)
   OR (n1.feat2 = n2.feat2 AND n1.feat2 = n3.feat2);
\end{verbatim}

NOTE: transitive closure of a graph can be
incrementally maintained: if node $x$ is added, for each neighbor $y$
of $x$ add distance; then for each other node $z$, add distance as:
distance to $y$ plus distance from $y$ to $x$.


References

[1]
http://en.wikipedia.org/wiki/Graph\_(data\_structure)\#Representations

[2] http://willets.org/sqlgraphs.html

[3] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.53

[4]
http://sqlblog.com/blogs/alexander\_kuznetsov/archive/2009/06/25/scalar-udfs-wrapped-in-check-constraints-are-very-slow-and-may-fail-for-multirow-updates.aspx

[5] http://www.dbazine.com/oracle/or-articles/tropashko8

[6] http://en.wikipedia.org/wiki/Collaborative\_filtering



[9]
http://bakara.eng.tau.ac.il/~semcomm/slides7/grouplensAlgs-Kahn.pps

[10]
http://www.slideshare.net/denisparra/evaluation-of-collaborative-filtering-algorithms-for-recommending-articles-on-citeulike

[11] http://virtuoso.openlinksw.com/

[12] http://www.openlinksw.com/weblog/oerling/?id=1433

[13] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.53

[14] http://en.wikipedia.org/wiki/Transitive\_reduction

\subsection{Collaborative Filtering in SQL}

Slope One: [7] http://en.wikipedia.org/wiki/Slope\_One

From
[8]
http://blog.charliezhu.com/2008/07/21/implementing-slope-one-in-t-sql/

\begin{verbatim}
create table UserData (                  -- fact table
    userid   varchar(50) not null,
    itemid   varchar(50) not null,
    rating   float not null default 0,
    updtime  datetime default getdate(),
    primary key (userid, itemid)
)

create table FreqDiff (                  -- Freqs and Diffs
    itemid1  varchar(50),
    itemid2  varchar(50),
    freq     float not null default 0,
    diff     float not null default 0,
    updtime  datetime default getdate(),
    primary key (itemid1, itemid2)
)
\end{verbatim}
After data table is filled:

\begin{verbatim}
insert into FreqDiff
select ud1.itemid, ud2.itemid, count(*), 
       (sum(ud1.rating - ud2.rating))/count(*), getdate()
from 
    userdata ud1 
    join userdata ud2 on 
            ud1.userid = ud2.userid
        and ud1.itemid > ud2.itemid
group by ud1.itemid, ud2.itemid

alter view vw_freqdiff as
select itemid1 as itemid1, itemid2 as itemid2, freq,     diff from FreqDiff fd
union all
select itemid2 as itemid1, itemid1 as itemid2, freq, -1* diff from
FreqDiff fd

-- predict process
declare @pref table(itemid varchar(50), rating float)
insert into @pref values('i1', 0.4)

select -- distinct top 10
    itemid1,
    sum(freq)                               as freq,
    sum(freq*(diff + rating))            as pref,
    sum(freq*(diff + rating)) /sum(freq) as rating
from 
    vw_freqdiff fd
    join @pref p on fd.itemid2 = p.itemid
where itemid1 not in( select itemid from @pref )
group by itemid1
\end{verbatim}

Compare this to other matrix operations in SQL.
